"""
最长系列
"""


class Solution:
    def longestCommonPrefix(self, strs):
        """
        最长公共前缀
        编写一个函数来查找字符串数组中的最长公共前缀。
        如果不存在公共前缀，返回空字符串 ""。
        输入: ["flower","flow","flight"]
        输出: "fl"
        :type strs: List[str]
        :rtype: str
        """
        # 按位压缩然后使用set去重复，如果大于1代表之前的就是公共前缀数组
        if not strs:
            return ""
        for i, letter_group in enumerate(zip(*strs)):
            if len(set(letter_group)) > 1:
                return strs[0][:i]
        else:
            # 防止元素内部就存在重复的字符
            return min(strs)

    def longestConsecutive(self, nums):
        """
        最长连续序列给定一个未排序的整数数组，找出最长连续序列的长度。
        要求算法的时间复杂度为 O(n)。
        输入: [100, 4, 200, 1, 3, 2]
        输出: 4
        解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
        :type nums: List[int]
        :rtype: int
        """
        # 动态规划使用字典存储
        dp = {}
        maxl = 0
        for x in nums:
            if x not in dp:
                l = dp.get(x-1,0)
                r = dp.get(x+1,0)
                cur = l + r + 1
                maxl = max(cur, maxl)
                dp[x] = cur
                dp[x-l] = cur
                dp[x+r] = cur
        return maxl

    def lengthOfLIS(self, nums):
        """
        最长上升子序列
        :type nums: List[int]
        :rtype: int
        """
        dp = [1]*len(nums)
        for i, x in enumerate(nums):
            j = 0
            while j < i:
                if x > nums[j]:
                    # 因为 i 之前的元素都已经比较过了所以只需要再比较 x 与之前的就行了
                    dp[i] = max(dp[i], dp[j]+1)
                j += 1
        return max(dp) if nums else 0

    def longestPalindrome(self, s):
        """
        最长回文子串
        :param s:
        :return:
        """
        n = len(s)
        maxl, start = 0, 0
        for i in range(n):
            if i-maxl >= 1 and s[i-maxl-1:i+1] == s[i-maxl-1:i+1][::-1]:
                start = i - maxl - 1
                maxl += 2
                continue
            if i-maxl >= 0 and s[i-maxl:i+1] == s[i-maxl:i+1][::-1]:
                start = i - maxl
                maxl += 1
        return s[start: start+maxl]

    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = {}
        res = 0
        for x in nums:
            dp[x] = dp.get(x, 0)+1
            if x + 1 in dp:
                res = max(res, dp[x + 1] + dp[x])
            if x - 1 in dp:
                res = max(res, dp[x - 1] + dp[x])
        return res

if __name__ == '__main__':
    s = Solution()
    res = s.findLHS([1,3,2,2,5,2,3])
    print(res)